#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> partition(vector<int>& arr, int left, int right){
    int pivot_idx = left + rand() % (right - left + 1);
    swap(arr[left], arr[pivot_idx]);
    int pivot = arr[left];

    int lt = left;      // [left, lt)区间的元素都小于pivot
    int gt = right;     // (gt, right]区间的元素都大于pivot
    int i = left + 1;   // 当前处理的元素

    while(i <= gt){
        if(arr[i] < pivot){
            swap(arr[i], arr[lt]);
            lt++;
            i++;
        }
        else if(arr[i] > pivot){
            swap(arr[i], arr[gt]);
            gt--;
        }
        else{
            i++;
        }
    }
    return {lt, gt};
}

void quickSort3Way(vector<int>& arr, int left, int right){
    if(left >= right) return;
    auto[lt, gt] = partition(arr, left, right);
    quickSort3Way(arr, left, lt -1);
    quickSort3Way(arr, gt + 1, right);
}

void quickSort3Way(vector<int>& arr){
    if(arr.empty()) return;
    srand(time(nullptr));
    quickSort3Way(arr, 0, arr.size() - 1);
}

int main(){
    vector<int> arr = {3,1,4,5,6,7,9,0};
    quickSort3Way(arr);
    for(int& x : arr){
        cout << x << " ";
    }
    return 0;
}   